package ai;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;

public class AIGraph<V> extends WeightedGraph<V> {

	// nodes left to visit from neighbors
	List<Integer> nodesToVisit = new ArrayList<Integer>();
	// nodes already visited (compared when checking neighbors)
	List<Integer> visitedNodes = new ArrayList<Integer>();

	public AIGraph(List<WeightedEdge> edges, List<V> vertices) {
		super(edges, vertices);
	}

	public void generateDistanceToGoal(int index) {
		City endCity = (City) vertices.get(index);
		int verticesSize = vertices.size();
		for (int i = 0; i < verticesSize; i++) {
			((City) vertices.get(i)).setDistanceToGoal(endCity);
		}
	}

	public double getRoadDistance(int currentCity, int nextCity) {
		PriorityQueue<WeightedEdge> list = queues.get(currentCity);
		Iterator<WeightedEdge> it = list.iterator();
		while (it.hasNext()) {
			WeightedEdge currentEdge = it.next();
			if (currentEdge.v == nextCity) {
				return currentEdge.weight;
			}
		}
		// error
		return -1;
	}

	public String findCityName(int index) {
		return ((City) vertices.get(index)).getCityName();
	}

	public int findCity(String cityName) {
		int vectorNumber = -1;
		int verticesSize = vertices.size();
		for (int i = 0; i < verticesSize; i++) {
			if (((City) vertices.get(i)).getCityName().equals(cityName)) {
				vectorNumber = i;
			}
		}
		return vectorNumber;
	}

	public String AIdfs(int startCity, int endCity) {
		// Clear lists to prepare for path.
		nodesToVisit.clear();
		visitedNodes.clear();
		StringBuilder results = new StringBuilder();
		results.append("DFS PATH \n");
		// turn found to true if goal is found
		boolean found = false;
		// form one-element queue consisting of a zero-length path
		// that contains only the root node
		nodesToVisit.add(startCity);
		System.out.println(printFSSet(nodesToVisit));
		// make list to store neighbors
		List<Integer> neighbors;
		// until the first path in the queue terminates at the goal node
		// or the queue is empty,
		while (!nodesToVisit.isEmpty() || found == true) {
			// if goal is the city at the head of the list, break from loop.
			if (nodesToVisit.get(0) == endCity) {
				results.append("* " + getVertex(endCity) + " *");
				found = true;
				break;
			}
			// find all neighbors of current node (head of path) &
			// remove the first node from the path
			int currentNode = nodesToVisit.remove(0);
			System.out.println(printFSSet(nodesToVisit));
			results.append(getVertex(currentNode) + "(");
			neighbors = getNeighbors(currentNode);
			Collections.sort(neighbors);
			// add currentNode to list vistedNodes
			visitedNodes.add(currentNode);
			// create a new path by extending the first path to all neighbors of
			// the terminal,
			// reject all new paths with loops (loop through neighbors, add new
			// neighbors to
			// front of the queue.
			int lastNeighbor = neighbors.size() - 1;
			for (int i = lastNeighbor; i >= 0; i--) {
				results.append(getVertex(neighbors.get(i)) + ", ");
				if (!visitedNodes.contains(neighbors.get(i))) {
					nodesToVisit.add(0, neighbors.get(i));
					System.out.println(printFSSet(nodesToVisit));
				}
			}
			// insert code here to return correct results string
			results.deleteCharAt(results.length() - 1);
			results.deleteCharAt(results.length() - 1);
			results.append(")\n");
		}
		return results.toString();
	}

	public String AIdfs(V startCity, V endCity) {
		String results = AIdfs(getIndex(startCity), getIndex(endCity));
		return results;
	}

	public String AIbfs(int startCity, int endCity) {
		// Clear lists to prepare for path.
		nodesToVisit.clear();
		visitedNodes.clear();
		StringBuilder results = new StringBuilder();
		results.append("DFS PATH \n");
		// turn found to true if goal is found
		boolean found = false;
		// form one-element queue consisting of a zero-length path
		// that contains only the root node
		nodesToVisit.add(startCity);
		System.out.println(printFSSet(nodesToVisit));
		// make list to store neighbors
		List<Integer> neighbors;
		// until the first path in the queue terminates at the goal node
		// or the queue is empty,
		while (!nodesToVisit.isEmpty() || found == true) {
			// if goal is the city at the head of the list, break from loop.
			if (nodesToVisit.get(0) == endCity) {
				results.append("* " + getVertex(endCity) + " *");
				found = true;
				break;
			}
			// find all neighbors of current node (head of path) &
			// remove the first node from the path
			int currentNode = nodesToVisit.remove(0);
			System.out.println(printFSSet(nodesToVisit));
			results.append(getVertex(currentNode) + "(");
			neighbors = getNeighbors(currentNode);
			Collections.sort(neighbors);
			// add currentNode to list vistedNodes
			visitedNodes.add(currentNode);
			// create a new path by extending the first path to all neighbors of
			// the terminal,
			// reject all new paths with loops (loop through neighbors, add new
			// neighbors to
			// back of the queue.
			int lastNeighbor = neighbors.size() - 1;
			for (int i = lastNeighbor; i >= 0; i--) {
				results.append(getVertex(neighbors.get(i)) + ", ");
				if (!visitedNodes.contains(neighbors.get(i))) {
					nodesToVisit.add(neighbors.get(i));
					System.out.println(printFSSet(nodesToVisit));
				}
			}
			// insert code here to return correct results string
			results.deleteCharAt(results.length() - 1);
			results.deleteCharAt(results.length() - 1);
			results.append(")\n");
		}
		return results.toString();
	}

	public String AIbfs(V startCity, V endCity) {
		String results = AIbfs(getIndex(startCity), getIndex(endCity));
		return results;
	}

	/**THIS ALGORYTHIM WAS IMPLEMENTED FROM PSEUDOCODE FOUND IN THE WIKIPEDIA ARTICLE ON A-STAR*/
	public String AIastar(int startCity, int endCity) {
		// prepare for a* (generate distance to goal for all cities)
		generateDistanceToGoal(endCity);
		ArrayList<Integer> closedSet = new ArrayList<Integer>();
		ArrayList<Integer> openSet = new ArrayList<Integer>();
		HashMap<Integer, Integer> cameFrom = new HashMap<Integer, Integer>();

		openSet.add(startCity);
		System.out.println(printSet(openSet));

		double[] g_score = new double[vertices.size()];
		g_score[startCity] = 0;
		double[] h_score = new double[vertices.size()];
		h_score[startCity] = ((City) vertices.get(startCity))
				.getDistanceToGoal();
		double[] f_score = new double[vertices.size()];
		f_score[startCity] = g_score[startCity] + h_score[startCity];

		boolean tentative_is_better = false;

		while (!openSet.isEmpty()) {
			int x = openSet.remove(0);
			System.out.println(printSet(openSet));
			if (x == endCity) {
				return reconstruct_path(cameFrom, cameFrom.get(endCity))
						+ " : " + findCityName(endCity);
			}

			closedSet.add(x);
			List<Integer> neighbors = getNeighbors(x);
			for (int i = 0; i < neighbors.size(); i++) {
				int y = neighbors.get(i);
				if (!closedSet.contains(y)) {

					double tentative_g_score = g_score[x]
							+ getRoadDistance(x, y);

					if (!openSet.contains(y)) {
						openSet.add(y);
						System.out.println(printSet(openSet));
						tentative_is_better = true;
					} else if (tentative_g_score < g_score[y]) {
						tentative_is_better = true;
					} else {
						tentative_is_better = false;
					}

					if (tentative_is_better == true) {
						cameFrom.put(y, x);
						g_score[y] = tentative_g_score;
						h_score[y] = ((City) vertices.get(y))
								.getDistanceToGoal();
						f_score[y] = g_score[y] + h_score[y];
					}
				}
			}
		}
		return "failure.";
	}

	String reconstruct_path(HashMap<Integer, Integer> cameFrom, int currentNode) {
		if (cameFrom.containsKey(currentNode)) {
			String p = reconstruct_path(cameFrom, cameFrom.get(currentNode));
			return p + " : " + findCityName(currentNode);
		} else {
			return "" + findCityName(currentNode);
		}
	}

	String printSet(List<Integer> cities) {
		StringBuilder results = new StringBuilder("{ ");

		for (int i = 0; i < cities.size(); i++) {
			results.append(findCityName(cities.get(i)) + ", ");
		}
		results.append(" }");
		return results.toString();
	}

	String printFSSet(List<Integer> cities) {
		StringBuilder results = new StringBuilder("{ ");

		for (int i = 0; i < cities.size(); i++) {
			results.append(getVertex(cities.get(i)) + ", ");
		}
		results.append(" }");
		return results.toString();
	}

	public String AIastar(String startCity, String endCity) {
		String results = AIastar(findCity(startCity), findCity(endCity));
		return results;
	}
}